package 牛客.二叉树;

import 剑指offer.TreeNode;

import java.util.Scanner;

public class BM39序列化二叉树 {
    String Serialize(TreeNode root) {
        //序列化
        if (root==null) {
            return "#";
        }
        StringBuilder res=new StringBuilder();
        SerializeFunction(root,res);
        return res.toString();

    }

    private void SerializeFunction(TreeNode root, StringBuilder str){
        if (root==null) {
            str.append("#");
            return;
        }
        //根节点,对每个当前根节点后面拼接！
        str.append(root.val).append('!');

        SerializeFunction(root.left,str);
        SerializeFunction(root.right,str);

    }

    private static int index=0;
    TreeNode Deserialize(String str) {
        //反序列化
        if (str == "#") {
            return null;
        }
        TreeNode root=DeserializeFunction(str);
        return root;
    }

    private TreeNode DeserializeFunction(String str) {
        if (str.charAt(index)=='#') {
            index++;
            return null;
        }

        int val=0;//用来构造节点的val
        //不是分隔符或者到字符串结尾
        while (str.charAt(index)!='!') {
            val=val*10+str.charAt(index)-'0';
            index++;
        }
        TreeNode root=new TreeNode(val);

        index++;

        root.left=DeserializeFunction(str);
        root.right=DeserializeFunction(str);

        return root;
    }

}
